package com.lans.alg;

/**
 * @author: lans
 * @date: 2025/3/11
 * @name: 刘宇
 */
public class Dyanmic {
    public static void main(String[] args) {
        int[][] arry = {{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
    }

    public static int dyanmic(int[][] arry) {
        if(arry.length==0){
            return 0;
        }
        //记录走过的路径位置
        int[][]dp = new int[arry.length][arry[0].length];
        dp[0][0] = arry[0][0];
        for(int i=1;i<dp[0].length;i++){
            //最小路径是左边的元素+自身的元素
            dp[0][i]=dp[0][i-1]+arry[0][i];
        }
        for(int i=1;i<arry.length;i++){//遍历列
            for(int j=0;j<dp[i].length;j++){
                if(j==0){
                    dp[i][j]=dp[i-1][j]+arry[i][j];
                }else if(dp[i-1][j]<dp[i][j-1]){
                    dp[i][j]=dp[i-1][j]+arry[i][j];
                }else{
                    dp[i][j]=dp[i][j-1]+arry[i][j];
                }
            }
        }
        return dp[dp.length-1][dp[dp.length-1].length-1];
    }
}